package com.yoshino.leetcode.oneHundred.twentyeighth;

import java.util.*;

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode cur;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (cur != null) {
                sb.append(cur.val + ",");
                queue.add(cur.left);
                queue.add(cur.right);
            } else {
                sb.append("null,");
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if ("[]".equals(data)) {
            return null;
        }
        String[] split = data.substring(1, data.length() - 1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        TreeNode cur;
        int i = 1;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (!"null".equals(split[i])) {
                cur.left = new TreeNode(Integer.parseInt(split[i]));
                queue.add(cur.left);
            }
            i++;
            if (!"null".equals(split[i])) {
                cur.right = new TreeNode(Integer.parseInt(split[i]));
                queue.add(cur.right);
            }
            i++;
        }
        return root;
    }

    List<String> list;
    boolean[] visited;
    public String[] permutation(String s) {
        int n = s.length();
        visited = new boolean[n];
        list = new ArrayList<>();
        char[] chars = s.toCharArray();
        // 为后续出现重复元素进行优化
        Arrays.sort(chars);
        StringBuilder sb = new StringBuilder();
        backtrack(chars, 0, n, sb);
        String[] res = new String[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private void backtrack(char[] chars, int ind, int n, StringBuilder sb) {
        if (ind == n) {
            list.add(sb.toString());
            return;
        }
        for (int i = 0; i < n; i++) {
            // 已经访问过
            // 当前访问的字符和前一个字符相等，且前一个字符为访问过（表示结果已经开始重复
            if (visited[i] || (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1] )) {
                continue;
            }
            visited[i] = true;
            sb.append(chars[i]);
            backtrack(chars, ind + 1, n, sb);
            sb.deleteCharAt(sb.length() - 1);
            visited[i] = false;
        }
    }
}